package 代码随想录.栈与队列.有效的括号字符串;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode678 {
    public static boolean checkValidString(String s) {
        Deque<Integer> leftStack = new LinkedList<>();    //左括号栈
        Deque<Integer> asterisStack = new LinkedList<>(); //星号栈
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftStack.push(i);  //碰到左括号，入左括号栈
            } else if (c == '*') {   //碰到星号栈
                asterisStack.push(i);
            } else {  //碰到右括号
                if (!leftStack.isEmpty()) {//如果左括号不为空，左括号栈顶元素出栈
                    leftStack.pop();
                } else if (!asterisStack.isEmpty()) {  //如果左括号栈为空，则从星号栈出栈
                    asterisStack.pop();
                } else {  //左括号栈和星号栈都为空，这时候碰到了右括号，则直接返回false
                    return false;
                }
            }
        }
        //遍历完成之后，若左括号栈和星号栈都有剩余
        while (!leftStack.isEmpty() && !asterisStack.isEmpty()) {
            //左括号栈和星号栈的元素对应出栈
            int leftIndex = leftStack.pop();
            int asteriskIndex = asterisStack.pop();
            //这个时候星号栈的元素就充当右括号，且右括号的下标必须大于左括号，否则直接false
            if (leftIndex > asteriskIndex) {
                return false;
            }
        }
        //如果最后左括号栈为空，返回true,星号栈无所谓，因为可以当作空字符串对待
        return leftStack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(checkValidString("()"));
        System.out.println(checkValidString("(*)"));
        System.out.println(checkValidString("(*))"));
        System.out.println(checkValidString("()*))"));
    }
}
